import java.util.*;

public class Test {
    public static void swap(int []array,int i , int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j]=tmp;
    }
    public static int parition(int[]array, int left, int right){
        int key =array[left];
        int i = left;
        while(left<right){
            while(left<right&&array[right]>=key){
                right--;
            }
            while(left<right&&array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return  left;
    }
    public static void quickSortNor(int[] array){
        Queue<Integer> queue = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
        int pivot = parition(array,left,right);
        if(pivot-1>left){
            queue.offer(left);
            queue.offer(pivot-1);
        }
        if(pivot+1<right){
            queue.offer(pivot+1);
            queue.offer(right);
        }
        while(!queue.isEmpty()){
            left=queue.poll();
            right=queue.poll();
            pivot = parition(array,left,right);
            if(pivot-1>left){
                queue.offer(left);
                queue.offer(pivot-1);
            }
            if(pivot+1<right){
                queue.offer(pivot+1);
                queue.offer(right);
            }
        }
    }

    public static void main(String[] args) {
        int [] array ={5,2,8,2,9,5,1,3,7};
        quickSortNor(array);
        System.out.println(Arrays.toString(array));
    }
}